package algorithm.variousAlgorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName: NetworkBecomesIdle
 * @Description 2039. 网络空闲的时刻
 * 给你一个有 n个服务器的计算机网络，服务器编号为0到n - 1。同时给你一个二维整数数组edges，其中edges[i] = [ui, vi]表示服务器ui和vi之间有一条信息线路，
 * 在一秒内它们之间可以传输任意数目的信息。再给你一个长度为n且下标从0开始的整数数组patience。
 *
 * 题目保证所有服务器都是 相通的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
 *
 * 编号为0的服务器是主服务器，其他服务器为数据服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按最优线路传输，
 *
 * 也就是说每个信息都会以 最少时间到达主服务器。主服务器会处理所有新到达的信息并立即按照每条信息来时的路线 反方向 发送回复信息。
 *
 * 在 0秒的开始，所有数据服务器都会发送各自需要处理的信息。从第1秒开始，每一秒最开始时，每个数据服务器都会检查它是否收到了主服务器的回复信息（
 *
 * 包括新发出信息的回复信息）：如果还没收到任何回复信息，那么该服务器会周期性重发信息。数据服务器i每patience[i]秒都会重发一条信息，也就是说，
 *
 * 数据服务器i在上一次发送信息给主服务器后的patience[i]秒后会重发一条信息给主服务器。否则，该数据服务器不会重发信息。
 *
 * 当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲状态。
 *
 * 请返回计算机网络变为 空闲状态的最早秒数。
 *
 * @Author skywingking
 * @Date 2022/3/20 7:49 下午
 **/
public class NetworkBecomesIdle {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; ++i) {
            adj[i] = new ArrayList<>();
        }
        boolean[] visit = new boolean[n];
        for (int[] v : edges) {
            adj[v[0]].add(v[1]);
            adj[v[1]].add(v[0]);
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        visit[0] = true;
        int dist = 1;
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                for (int v : adj[curr]) {
                    if (visit[v]) {
                        continue;
                    }
                    queue.offer(v);
                    int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
                    ans = Math.max(ans, time);
                    visit[v] = true;
                }
            }
            dist++;
        }
        return ans;
    }
}